package com.leetcode.algorithm.y22.m05;

import java.util.Arrays;

/**
 * 509. 斐波那契数 
 * https://leetcode.cn/problems/fibonacci-number/
 * 
 * @author jie.deng
 *
 */
class Question0509Solution04 {

	// 递归 + 备忘录
	public int fib(int n) {
		if (n <= 1) {
			return n;
		}

		int[] memo = new int[n + 1];
		Arrays.fill(memo, -1);
		memo[0] = 0;
		memo[1] = 1;
		return doFib(n, memo);
	}

	private int doFib(int n, int[] memo) {
		if (memo[n] == -1) {
			memo[n] = doFib(n - 1, memo) + doFib(n - 2, memo);
		}
		return memo[n];
	}

}